package org.example.algorithm.array;

//12385764
public class NextPermutationSolution {
    public static void main(String[] args) {
        int nums[] = {2, 3, 1};
        NextPermutationSolution solution = new NextPermutationSolution();
        solution.nextPermutation(nums);
        for (int i=0;i<nums.length;i++) {
            System.out.println(nums[i]);
        }
    }

    public void nextPermutation(int[] nums) {
        int len = nums.length;
        if (len <= 1) {
            return;
        }
        //倒序查找第一个升序起点
        int from = -1;
        for (int i=len-2;i>=0;i--) {
            if (nums[i] < nums[i+1]) {
                from = i;
                break;
            }
        }
        if (from == -1) {
            reverse(nums, 0);
            return;
        }
        //倒序查找第一个比from位置大的元素
        int to = len-1;
        for (int i=len-1;i>=0;i--) {
            if (nums[i] > nums[from]) {
                to = i;
                break;
            }
        }
        swap(nums, from, to);
        reverse(nums, from+1);
    }

    private void reverse(int[] nums, int from) {
        int to = nums.length-1;
        while (from < to) {
            swap(nums, from, to);
            from++;
            to--;
        }
    }

    private void swap(int[] nums, int from, int to) {
        int temp = nums[from];
        nums[from] = nums[to];
        nums[to] = temp;
    }
}
